Global register allocation is an on-going problem in the design and optimization of compiler performance. The problem is to reduce a large number of symbolic registers down to a small finite number of hardware registers. Whenever this is not possible, some registers must be stored in memory and re-loaded only when needed. These registers are referred to as "spilled" registers.
Most compilers assume an arbitrarily large number of registers during their optimization procedures. In fact the result of each different computation in the program is conventionally assigned a different symbolic register. At this point a register allocation procedure must be invoked to assign real, i.e. hardware registers, from those available in the machine, to these symbolic registers. Conventional approaches use a subset of the real registers for special purposes while the remaining set is assigned locally within the statement, or at best the basic block (e.g. a loop). Between these assignments, results which are to be preserved are temporarily stored, and variables are redundantly reloaded. While these approaches clearly work, they are inefficient in that a significant amount of processor (i.e. CPU) time is wasted while data is being transferred between memory storage and registers or conversely, data is accessed from and returned to storage directly bypassing the registers completely.
Graph colouring is a well-known technique for allocating registers during compilation. The graph colouring technique is based on the observation that the register assignment or allocation problem is equivalent to the graph colouring problem, where each symbolic register is a node and the real, i.e. hardware, registers are different colours. When two symbolic registers have the property that there is at least one point in the program when both their values must be retained, that property is modelled on the graph as a vertex or edge between the two nodes. Thus the register allocation problem is equivalent to the problem of colouring the graph so that no two nodes connected by a vertex are coloured the same. This is equivalent to saying that each of these two (or more) nodes must be stored in different registers.
Two main approaches exist for global register allocation using graph colouring. The first is known as the Chaitin style graph colouring by Gregory J. Chaitin. The Chaitin technique has been enhanced by Preston P. Briggs at Rice University.
According to the Chaitin graph colouring technique, two symbolic registers are said to interfere if they are live, i.e. contain a value, at the same time. This means that the two symbolic registers cannot occupy the same hardware or machine register. The degree of a register is defined as the number of other registers which interfere with it.
A pass is made through the program to build an interference graph. The interference graph summarizes what symbolic registers interfere with each other, and each symbolic register is represented by a node in the graph. Once the interference graph is built, graph reduction is attempted. Any register whose degree is less than the number of hardware a registers, i.e. "colours", is removed from the graph, and pushed onto a reduction stack. According to the Chaitin technique, if a node has less interferences than the number of hardware registers, then there must be a hardware register that can be assigned to the node, i.e. symbolic register. When a node is removed, the degree of all its neighbours is reduced by one. This reduction process is continued until either the graph is empty, signifying successful colouring, or all remaining nodes have a degree that is too high to be reduced.
If nodes remain, one of the nodes, i.e. symbolic registers, is chosen for spilling (i.e. storage in memory). There are various heuristics, and how the choice is made will be apparent to one skilled in the art. Accordingly, one of the remaining nodes is chosen and marked to "spill"; the selected node is then pushed onto the reduction stack, and removed from the interference graph. The reduction operation is repeated on the graph with the remaining nodes in an attempt to further reduce the number of nodes (i.e. symbolic registers). The reduction process is repeated until the graph completely reduces. In complex programs with numerous symbolic registers, many registers will be marked to spill.
Once the reduction operation has been completed, the symbolic registers are assigned to colours (i.e. hardware registers). Initially, each symbolic register can be assigned any available colour or hardware register. The symbolic registers are removed from the reduction stack, and as each symbolic is removed, the lowest available colour number for that register is assigned to the symbolic. Next all the neighbours of the symbolic register in the interference graph are visited, and the assigned colour is removed from their available colour list. This prevents any registers which interfered from choosing the same colour.
According to the Chaitin technique, any symbolic register which was reduced normally, i.e. not spilled, is guaranteed to be given a colour, i.e. assigned a hardware register. Such a symbolic register is said to have been proven. Conversely, any symbolic register that was marked to spill is not expected to get a colour. Sometimes symbolic register marked to spill will end with a colour, and this is the `optimistic` approach developed by Briggs. In any case, according to Chaitin spill code needs to be generated for a symbolic register which cannot be given a colour.
Another pass is made through the program, and any reference to a symbolic register which is marked to spill is replaced with either a memory load or store. It will be appreciated that this operation effectively splits the live range of the spilled registers to very local occurrences where they are used or defined.
Once the spill code has been generated, the reduction process is repeated starting with building a new interference graph. The cycle is repeated until the graph successfully reduces. In many cases, multiple iterations of colouring are required to successfully reduce a graph, i.e. assign all the data items (i.e symbolic registers) to machine registers and memory storage.
The Chaitin style graph colouring technique has been found to work quite well. However, problems with the Chaitin technique arise when there are more data items to be retained than there are machine registers available. As described above, when the data items (i.e. symbolic registers) exceed the number of machine registers "spilling" of the symbolic registers into memory is necessary.
The generation of efficient spill code is not trivial. The approach according to Chaitin required that a load to memory be issued at each use point of a spilled symbolic. Following this approach, if there are two uses of a symbolic register on consecutive instructions, it is preferable to only perform the memory load once, and use the data item on both instructions. Similarly, if the two uses of the symbolic register are just close together, it is advantageous to perform the memory load once and re-use the data item. With the Chaitin approach, as the live range of a re-used spill is extended, there is the risk that a new interference will be caused which will require another pass of colouring.
Most programs will have `hot spots` which have high register pressure. These are the areas in a program which cause most of the spilling of the data items (i.e. symbolic registers). When a symbolic register is chosen to be spilled, the register is spilled everywhere even in other areas where there is no interference with the symbolic register. This is an artifact of global spilling. No local information is available about individual uses of a register, just the global interference graph.
To improve register allocation several approaches have been developed in the art.
Rematerialization is one known approach where the value of the symbolic register is recalculated instead of loading the data item from memory. Rematerialization reduces the number of memory stores which need to be spilled.
Another approach involves partitioning the interference or flow graph and colouring the different partitions separately. This approach attempts to reduce the global effect of spilling, so that if a symbolic register spills in one partition, the register doesn't need to spill in the other partitions. While this approach is workable, problems usually arise with "patch-up" code for bridging the partitions.
In another approach, the register sets are split into two groups: global and local registers. The global symbolic registers are assigned to the global hardware registers, and then a local allocation is performed to assign the remaining registers. While this approach is workable, it does not always result in optimal good global allocations because all the registers are not available.
According to another approach, "live range" splitting is performed before the colouring (i.e. reduction) process. In this approach, any registers with long live ranges over high pressure or "hot" regions in the program are stored before entry and loaded after exit to the region. This makes the register(s) appear to be a different register in the high pressure region.
The graph colouring approach according to Chaitin/Briggs has proven very effective. Experience has shown that many procedures "colour" so that no store-load operations are necessary to keep results in storage temporarily. On the down side, the Chaitin/Briggs requires large amounts of compile time.
Therefore, a need remains for a register allocator which requires less computation time, and which also provides a better approach to the spilling problem.